package dp;

import java.util.Arrays;

public class KnapsackProblem {

    static class Item {
        int index;
        String name;
        int weight;
        Integer value;

        public Item(int index, String name, int weight, Integer value) {
            super();
            this.index = index;
            this.name = name;
            this.weight = weight;
            this.value = value;
        }

    }

    public static void main(String[] args) {
        Item[] items = new Item[]{
                new Item(1, "黄金", 4, 1600),
                new Item(2, "宝石", 8, 2400),
                new Item(3, "白银", 5, 30),
                new Item(4, "钻石", 1, 10000)
        };
        select(items, 10);
    }

    public static void select(Item[] items, int total) {
        int[][] dp = new int[items.length][total + 1];
        for (int i = 0; i < total + 1; i++) {
            if (i >= items[0].weight) { //�b����
                dp[0][i] = items[0].value;
            } else {
                dp[0][i] = 0;
            }
        }
        for (int i = 1; i < dp.length; i++) {
            Item item = items[i];
            for (int j = 0; j < total + 1; j++) {
                if (j >= item.weight) { //装得下       当前物品重量 加上 剩余 空间重量最大值
                    dp[i][j] = Integer.max(dp[i - 1][j], item.value + dp[i - 1][j - item.weight]);
                } else { //装不下
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        print(dp);

    }

    private static void print(int[][] dp) {
        System.out.println("=====");
        for (int[] ints : dp) {
            System.out.println(Arrays.toString(ints));
        }
        System.out.println("=====");
    }
}
